#include "arbre.hpp"

void create_tree(tree & t)
{
  t=NULL;
}

void create_node(tree & t,chained_index & c_i)
{
  if(c_i != NULL)
    {
      // Initialisation dun noeud
      tree tmp;
      create_tree(tmp);

      // Allocation dun noeud
      tmp=new node;
      tmp->left=NULL;
      tmp->right=NULL;

      // Remplisage du noeud
      tmp->item=new s_item;
      // Redirection de c_i (chained_index)
      // Pour que cela fasse partie du noeud
      tmp->item->c_i=c_i;
      // Avancement du pointeur de c_i
      c_i=c_i->next;
      // Suppression du lien entre le noeud et la chained_index
      tmp->item->c_i->next=NULL;
      // Mise a jour du nombre de noeud
      tmp->item->nb_nodes=1;
      // Ratachement du noeud au reste de larbre
      t=tmp;
    }
}

void initialise_tree(tree & t,chained_index & c_i)
{
  while(c_i != NULL)
    {
      // Tree est vide alors 1 noeud
      // sinon on le rajoute au bon endroit
      if(t == NULL)
	{
	  create_node(t,c_i);
	}
      else
	{
	  // Le pointeur lecteur permet de lire chaque noeud
	  // sans detruire larbre
	  tree lecture=t;
	  bool non_null=true;
	  // Recherche de la position pour placer le noeud suivant
	  // de la c_i (chained_index)
	  while(non_null)
	    {
	      // Si le mot du pointeur de lecture < mot de c_i
	      // Sinon on verifie si le mot de lecture > mot de c_i
	      if(lecture->item->c_i->word < c_i->word)
		{
		  // Si le pointeur de lecture != NULL
		  // Alors on le bouge a droite
		  // en mettant a jour le nb de noeud
		  // SINON on est arriver et on sort de la boucle
		  if(lecture->right != NULL)
		    {
		      lecture->item->nb_nodes+=1;
		      lecture=lecture->right;
		    }
		  else
		    non_null=false;
		}
	      else
		if(lecture->item->c_i->word > c_i->word)
		  {
		    // Si le pointeur de lecture != NULL
		    // Alors on bouge a gauche
		    // en mettant a jour le nb de noeud
		    // SINON on est arriver et on sort de la boucle
		    if(lecture->left != NULL)
		      {
			lecture->item->nb_nodes+=1;
			lecture=lecture->left;
		      }
		    else
		      non_null=false;
		  }
	    }

	  // Si le mot de lecture < mot de c_i
	  // Alors on le place a droite et on maj le nb de noeud
	  // Sinon on le place a gauche et on maj le nb de noeud
	  if(lecture->item->c_i->word < c_i->word)
	    {
	      lecture->item->nb_nodes+=1;
	      create_node(lecture->right,c_i);
	    }
	  else
	    if(lecture->item->c_i->word > c_i->word)
	      {
		lecture->item->nb_nodes+=1;
		create_node(lecture->left,c_i);
	      }

	}
    }
  equilibre_tree(t);
}

void affiche_tree(const tree & t,int h)
{
  for(int i=0 ; i < h ; ++i)
    cout << "\t";

  if(t != NULL)
    {
      affiche_index(t->item->c_i);
      cout << "Nb noeud : " << t->item->nb_nodes << endl << endl;

      affiche_tree(t->left,++h);
      --h;
      affiche_tree(t->right,++h);
    }
  else
    cout << "~" << endl;
}

void delete_all_tree(tree & t)
{
  if(t != NULL)
    {
      delete_all_tree(t->left);
      // Suppression des fils gauche
      if(t->left != NULL)
	{
	  // Suppression de lindex
	  delete_all_index(t->left->item->c_i);
	  // Suppression de litem
	  delete t->left->item;
	  // Suppression du fils gauche
	  delete t->left;
	}
      delete_all_tree(t->right);
      // Suppression des fils droit
      if(t->right != NULL)
	{
	  // Suppression de lindex
	  delete_all_index(t->right->item->c_i);
	  // Suppression de litem
	  delete t->right->item;
	  // Suppression du fils droit
	  delete t->right;
	}
    }
}

void add_ligne_tree(tree & t,chained_word & c_w)
{
  tree lecture;
  string word;
  int ligne;

  while(c_w != NULL)
    {
      word=c_w->word;
      ligne=c_w->cpt;

      // Pointeur de lecture sur larbre
      lecture=t;

      // Tant que lecture != NULL ET le mot du noeud est different
      // du mot ds c_w alors on boucle
      while(lecture != NULL && lecture->item->c_i->word != word)
	{
	  // Si le mot du noeud < mot alors on va a droite
	  // Sinon si mot du noeud > mot alors on va a gauche
	  if(lecture->item->c_i->word < word)
	    lecture=lecture->right;
	  else
	    if(lecture->item->c_i->word > word)
	      lecture=lecture->left;
	}

      // Si le pointeur de lecture != NULL alors on a trouver le mot
      // Donc on le rajoute
      if(lecture != NULL)
	add_number_ligne(lecture->item->c_i,word,ligne);

      // Suppression du mot pour boucler
      delete_word(c_w);
    }
}

void partition_r(tree & t,int nb_noeud)
{
  int tmp_noeud(0);

  if(t->left != NULL)
    tmp_noeud=t->left->item->nb_nodes;

  if(tmp_noeud > nb_noeud)
    {
      partition_r(t->left,nb_noeud);
      rotation_right(t);
    }
  else
    if(tmp_noeud < nb_noeud)
      {
	partition_r(t->right,nb_noeud-tmp_noeud-1);
	rotation_left(t);
      }
}

void rotation_right(tree & t)
{
  tree tmp=t->left;
  int tmp_noeud(0),tmp_noeud_droit(0),tmp_noeud_gauche(0);
    
  if(t != NULL)
    tmp_noeud=t->item->nb_nodes;

  t->left=tmp->right;
  if(t->right != NULL)
    tmp_noeud_droit=t->right->item->nb_nodes;

  if(t->left != NULL)
    tmp_noeud_gauche=t->left->item->nb_nodes;

  t->item->nb_nodes=tmp_noeud_gauche+tmp_noeud_droit+1;

  tmp->right=t;
  t=tmp;
  t->item->nb_nodes=tmp_noeud;
}

void rotation_left(tree & t)
{
  tree tmp=t->right;
  int tmp_noeud(0),tmp_noeud_droit(0),tmp_noeud_gauche(0);
    
  if(t != NULL)
    tmp_noeud=t->item->nb_nodes;

  t->right=tmp->left;
  if(t->right != NULL)
    tmp_noeud_droit=t->right->item->nb_nodes;

  if(t->left != NULL)
    tmp_noeud_gauche=t->left->item->nb_nodes;

  t->item->nb_nodes=tmp_noeud_gauche+tmp_noeud_droit+1;

  tmp->left=t;
  t=tmp;
  t->item->nb_nodes=tmp_noeud;
}

void equilibre_tree(tree & t)
{
  // Partition en fonction de la medianne
  partition_r(t,t->item->nb_nodes/2);
}
